import time
import math
"""
is_prime最费时，因为它需要对每个数单独进行判断，并且对每个数都要进行多次取模运算，对于较大的数值范围，这种方法的效率会显著下降。
## 改进：
    埃拉托斯特尼筛法（sieve_of_eratosthenes()）时间复杂度为 O (n log log n)
    筛法的核心思想是：一旦确定一个数是素数，就将它所有的倍数标记为非素数
"""

def is_prime(n):
    """判断一个数是否为素数"""
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # 只需检查到sqrt(n)即可，且只检查奇数
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True


def sieve_of_eratosthenes(n):
    """使用埃拉托斯特尼筛法找出所有小于等于n的素数"""
    if n < 2:
        return []

    # 初始化一个布尔数组，表示每个数是否为素数
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for current in range(2, int(math.sqrt(n)) + 1):
        if is_prime[current]:
            # 标记当前数的所有倍数为非素数
            for multiple in range(current * current, n + 1, current):
                is_prime[multiple] = False

    # 收集所有素数
    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes


def print_primes(primes, per_line=5):
    """按每行指定数量打印素数"""
    for i, prime in enumerate(primes):
        # 格式化输出，保持对齐
        print(f"{prime:6}", end='')
        # 每per_line个素数换行
        if (i + 1) % per_line == 0:
            print()
    print()  # 最后换行


if __name__ == "__main__":
    # 测试两种方法的性能
    max_num = 20000

    # 测试逐个判断法
    start_time = time.time()
    primes1 = [i for i in range(max_num + 1) if is_prime(i)]
    time1 = time.time() - start_time

    # 测试埃拉托斯特尼筛法
    start_time = time.time()
    primes2 = sieve_of_eratosthenes(max_num)
    time2 = time.time() - start_time

    # # 打印结果（使用筛法的结果）
    # print(f"1~{max_num}内的所有素数：")
    # print_primes(primes2)

    print(f"\n逐个判断法耗时: {time1:.6f}秒")
    print(f"埃拉托斯特尼筛法耗时: {time2:.6f}秒")
    print(f"筛法比逐个判断法快约{time1 / time2:.1f}倍")
